import numpy as np

close_list = close_set = []
open_list = fringe = []
dis = 0
h = 0
g = 0
start = 0
route = 0
goal = 0
name = None
INF = 100000


def name_of(node):
	return name[node]


def print_route(now):
	if (now == start):
		print("%s->" % name_of(now), end='')
		return
	print_route(route[now])
	if (now == goal):
		print("%s . The cost is %d" % (name_of(now), g[goal]))
	else:
		print("%s->" % name_of(now), end='')


def best_in_the_open_list():
	minn = INF
	min_i = 0
	for i in open_list:
		if (g[i] + h[i] < minn):
			minn = g[i] + h[i]
			min_i = i
	return min_i


def AstarSearch(dis2, h2, start2, goal2, name2=None):
	global dis
	global h
	global g
	global start
	global goal
	global name
	global NODE_SIZE
	global route
	global close_list
	global open_list
	dis = dis2
	h = h2
	start = start2
	goal = goal2
	name = name2
	NODE_SIZE = len(dis)
	route = np.array([0] * NODE_SIZE)
	g=np.array([INF]*NODE_SIZE)

	g[start] = 0
	open_list.append(start)
	while (len(open_list) != 0):
		now = best_in_the_open_list()
		for i in range(0, NODE_SIZE, 1):
			if (i == now or dis[now][i] == INF or i in close_list):
				continue
			if (g[i] > g[now] + dis[i][now]):
				if (i not in open_list):
					open_list.append(i)
				route[i] = now
				g[i] = g[now] + dis[i][now]
		open_list.remove(now)
		if (now == goal):
			print_route(now)
			return True
		close_list.append(now)
	print("No solution found!")
	return False
